package other;

import java.util.Arrays;

public class D230902 {
    // 顺时针旋转矩阵
    // 矩阵顺时针旋转 90°
    public int[][] rotateMatrix (int[][] mat, int n) {
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res[i][j] = mat[n - 1 - j][i];
            }
        }
        return res;
    }

    // 分糖果问题
    // 贪心算法
    // 时间：O(n)
    // 空间：O(n)
    public int candy (int[] arr) {
        int n = arr.length;

        // 使用一个辅助数组，记录每个孩子分到的糖果，初始值为 1
        int[] a = new int[n];
        Arrays.fill(a, 1);

        // 从左到右遍历数组，如果右边元素比左边大，糖果就是左边元素 + 1
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) a[i] = a[i - 1] + 1;
        }


        // 从右到左遍历数组，如果左边元素更大，但是糖果不大于右边元素，糖果就是右边元素 + 1
        // 同时记录糖果总数
        int res = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1] && a[i] <= a[i + 1]) {
                a[i] = a[i + 1] + 1;
            }

            res += a[i];
        }
        return res;
    }
}
